package first

/*
	给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

	示例 1：
	输入：head = [1,2,2,1]
	输出：true

	示例 2：
	输入：head = [1,2]
	输出：false

	提示：
	链表中节点数目在范围[1, 105] 内
	0 <= Node.val <= 9

	进阶：你能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/palindrome-linked-list
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func isPalindrome(head *ListNode) bool {
	//1. 找链表的中点
	f, s := head, head
	for f != nil && f.Next != nil {
		f = f.Next
		f = f.Next
		s = s.Next
	}
	//2. 后半部分反转
	ret := reverse(s)
	//3. 比较前半部分和后半部分
	// 要不要断开
	for head != nil && ret != nil {
		if head.Val != ret.Val {
			return false
		}
		head = head.Next
		ret = ret.Next
	}
	//4. 复原链表
	return true
}

func reverse(head *ListNode) *ListNode {
	if nil == head {
		return head
	}
	if head.Next == nil {
		return head // 得到头节点
	}
	ret := reverse(head.Next)
	head.Next.Next = head
	head.Next = nil
	return ret
}
